package com.leetcode.August;

import java.util.Arrays;

/**
 * @Description: 动态规划
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-07 09:50
 */
public class LC322零钱兑换 {
    public int coinChange(int[] coins, int amount) {
        if (coins.length == 0 || coins == null) return -1;
        int[] dp = new int[amount + 1];//dp[i] 表示凑成金额 i 所需的最少硬币个数。
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for (int i = 1; i <=amount; i++) {
//这个条件确保了当前硬币面额 coin 不超过当前考虑的金额 i。这是因为如果硬币面额超过了当前的金额，那么这枚硬币就不可能被用来凑出这个金额，所以不需要考虑它
            for (int coin : coins) {
                if (coin<=i){
                    dp[i]=Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        return dp[amount]>amount ? -1:dp[amount];
        //dp[amount] 大于 amount，说明没有凑成 amount 的组合，返回 -1。
    }
/**
 * 第一行循环
 * for (int i = 1; i <= amount; i++): 这个循环遍历从 1 到 amount 的每一个可能的金额 i。
 * 内层循环
 * for (int coin : coins): 这个循环遍历 coins 数组中的每一个硬币面额 coin。
 * 条件判断
 * if (coin <= i): 这个条件确保了当前硬币面额 coin 不超过当前考虑的金额 i。这是因为如果硬币面额超过了当前的金额，那么这枚硬币就不可能被用来凑出这个金额，所以不需要考虑它。
 * 更新 dp[i]
 * dp[i] = Math.min(dp[i], dp[i - coin] + 1);: 这一行代码是动态规划算法的核心部分，用于更新 dp[i] 的值。
 * dp[i] 当前表示凑成金额 i 所需的最少硬币个数。
 * dp[i - coin] 表示凑成金额 i - coin 所需的最少硬币个数。
 * dp[i - coin] + 1 表示如果我们使用一枚面额为 coin 的硬币来凑出金额 i，那么所需的硬币总数就是凑出金额 i - coin 所需的硬币数再加上这一枚硬币。
 * 举例说明
 * 假设 coins 数组为 {1, 2, 5}，并且 amount 为 11。
 *
 * 当 i = 5 时，我们考虑使用 coins 中的每一枚硬币来凑出 5 这个金额。
 * 对于 coin = 1，dp[5 - 1] + 1 = dp[4] + 1，如果 dp[4] 是凑成金额 4 所需的最少硬币数，那么加上 coin = 1 后，所需硬币数就是 dp[4] + 1。
 * 对于 coin = 2，dp[5 - 2] + 1 = dp[3] + 1，如果 dp[3] 是凑成金额 3 所需的最少硬币数，那么加上 coin = 2 后，所需硬币数就是 dp[3] + 1。
 * 对于 coin = 5，dp[5 - 5] + 1 = dp[0] + 1，如果 dp[0] 是凑成金额 0 所需的最少硬币数（在这个情况下，dp[0] = 0），那么加上 coin = 5 后，所需硬币数就是 dp[0] + 1。*/

}
